\documentclass[paper=a4, fontsize=11pt]{scrartcl}
\newcommand{\bfvec}[1]{\mbox{\boldmath$#1$}}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{calligra,chancery,charter}
\usepackage[top=0.75in, bottom=1in, left=0.5in, right=0.5in]{geometry} 
\usepackage{amsmath,amssymb}
\title{	
\normalfont \normalsize 
\textsc{Shanghai Jiaotong University, Zhiyuan College} \\ [25pt]
\huge Homework 9 \\
}
\author{Feng Shi}
\date{\normalsize\today}
\begin{document}
\maketitle

\begin{enumerate}

\item[Ex 5.29]
{\Large Solution :}(combinatorial)\\
First we modify the problem by ``unfolding'' the $x-$axis, to as follows.

\begin{quote}
{\textsl{Consider a random walk on $x-$axis. When at position $x>0$, turn right with
probability $\frac{2}{3}$ and left with probability $\frac{1}{3}$. When at position
$x<0$, turn left with probability $\frac{2}{3}$ and right with probability 
$\frac{1}{3}$. Start the random walk at the origin. Calculate escape probability.}}
\end{quote}

This modification only changes the coordinate, not the behaviour of the random walk,
so it won't affect the escape probability.

And we consider a generalized problem: turing left with probability $p$ and right
with probability $1-p$ (starting at the origin).

\vspace{10pt}
Let $u_n$ be the probability that the walk is at the origin at step $n$.\\
Let $f_n$ be the probability that the walk returns $0$ \textbf{for the first time} at
step $n$.\\
Let $f$ be the probability that the walk returns to $0$, then the escape probability
is $(1-f)$.\\
And $$f=\sum_{n=1}^{\infty}f_n,\quad f_0=0,\quad u_n=0 \ for \ n=1,3,5,...$$
The recurrence is:
\begin{align*}
u_1&=f_0u_1+f_1u_0\\
u_2&=f_0u_2+f_1u_1+f_2u_0\\
& \ \ \vdots\\
u_n&=f_0u_n+f_1u_{n-1}+\cdots+f_nu_0
\end{align*}
Define \textbf{generating functions}
\begin{align*}
U(x)&=u_0+u_1x+u_2x^2+\cdots\\
F(x)&=f_0+f_1x+f_2x^2+\cdots
\end{align*}
And we have
$$U(x)F(x)=u_0f_0+(u_0f_1+u_1f_0)x+(u_0f_2+u_1f_1+u_2f_0)x^2+\cdots=U(x)-1$$

\textbf{Lemma 1.}
\begin{quote}
\textsl{If $\sum_{n=1}^{\infty}u_n=\infty$, the escape probability
is 0.}\\
\textsl{If $\sum_{n=1}^{\infty}u_n<\infty$, then the random walk has positive escape
probability.}
\end{quote}
\textbf{Proof:}(of lemma)\\
Since $u_n$ are non-negative
$$\forall N\in \mathbb{N} \  \sum_{n=1}^{N}u_n<\lim_{x\to 1}U(x)$$
So if $\sum_{n=1}^{\infty}u_n=\infty$, then $lim_{x\to 1}U(x)=\infty$.\\
Given $U(x)F(x)=U(x)-1$, $U(x)(1-F(x))=1$, we have
$$f=\lim_{x\to 1}F(x)=1$$
which means the escape probability is 0.\\
If $\sum_{n=1}^{\infty}<\infty$, 
$\lim_{x\to 1}U(x)=U(1)=\sum_{n=1}^{\infty}u_n<\infty$. Then by $U(x)(1-F(x))=1$ we
have $f=\lim_{x\to 1}F(x)<1$. So the random walk has positive escape probability.
$\quad\square$

\vspace{10pt}
Since $u_n=0$ for all odd $n$. $\sum_{n=1}^{\infty}u_n=\sum_{n=1}^{\infty}u_{2n}$.\\
There are totally $2^{2n}$ different routes for $2n$ steps. In order to return to $0$,
we need exactly $n$ left turns and $n$ right turns. That is $\binom{2n}{n}$
different routes.

\begin{align*}
	u_{2n}&=\binom{2n}{n}\frac{1}{2^{2n}}p^n(1-p)^n\\
	&=\frac{(2n)!}{(n!)^2}\frac{1}{2^{2n}}p^n(1-p)^n\\
	&\approx\frac{\sqrt{4\pi n} (\frac{2n}{e})^{2n}}{(\sqrt{2\pi n}(\frac{n}{e})^n)^2}
	\frac{1}{2^{2n}}p^n(1-p)^n \tag{by Stirling's approximation}\\
	&=\frac{1}{\pi n}p^n(1-p)^n\\
	&\approx \frac{1}{\pi n}(4p(1-p))^n
\end{align*}
Whenever $p\neq \frac{1}{2}$, $4p(1-p)<1$, and $(4p(1-p))^n$ approches $0$
exponentially fast.\\
so $\sum_{n=1}^{\infty}u_n=\sum_{n=1}^{\infty}u_{2n}<\infty$.
So this kind of unsymmetric $1-$dimensional random walk has positive escape probability.

Back to the origin problem(the modified one), no matter the walk is at $x<0$ or $x>0$.
the inequality $4p(1-p)<1$ always holds, so the original random walk also has
positive escape probability.

\vspace{20pt}
\newpage
\item[Ex 5.47]
{\Large Solution:}\\

Transition probability:

\begin{tabular}{c| c c c c c c c c c}
 & $(0,0)$ & $(0,1)$ & $(0,2)$ & $(1,0)$ & $(1,1)$ & $(1,2)$ & $(2,0)$ & $(2,1)$ & $(2,2)$ \\\hline\\
$(0,0)$ & $\frac{1}{2}$ & $\frac{1}{4}$ & $\frac{1}{4}$ &-&-&-&-&-&-\\ \\
$(0,1)$ & $\frac{1}{8}$ & $\frac{1}{2}$ & $\frac{1}{8}$ &-& $\frac{1}{4}$&-&-&-&- \\\\
$(0,2)$ & $\frac{1}{4}$ & $\frac{1}{2}$ & $\frac{1}{4}$&-&-&-&-&-&-\\\\
$(1,0)$ & $\frac{1}{8}$ &-&-& $\frac{1}{2}$ & $\frac{1}{4}$ & $\frac{1}{8}$&-&-&-\\\\
$(1,1)$ &-& $\frac{1}{8}$ &-& $\frac{1}{8}$ & $\frac{1}{2}$ & $\frac{1}{8}$ &-& $\frac{1}{8}$&-\\\\
$(1,2)$ &-&-&$\frac{1}{8}$ & & $\frac{1}{4}$ & $\frac{1}{2}$ &-&-& $\frac{1}{8}$ \\\\
$(2,0)$ &-&-&-& $\frac{1}{4}$ &-&-& $\frac{1}{2}$ & $\frac{1}{4}$&- \\\\
$(2,1)$ &-&-&-&-& $\frac{1}{4}$ &-& $\frac{1}{8}$ & $\frac{1}{2}$ & $\frac{1}{8}$ \\\\
$(2,2)$ &-&-&-&-&-& $\frac{1}{4}$ &-& $\frac{1}{4}$ & $\frac{1}{2}$

\end{tabular}
\vspace{20pt}
\end{enumerate} % end of questions
\end{document}

